580D - Kefa and Dishes - CodeForces Solution

#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cstring>
#include <vector>
#define fast_input ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace ::std;
#define int long long

int n, m, k;
vector<int> a;
int memo[1<<20][20];

int DP(int last, int bitmask, vector<vector<int>>& c) {
    if (__builtin_popcount(bitmask) == m) return 0;

    if (memo[bitmask][last] != -1) return memo[bitmask][last]; 
    memo[bitmask][last] = 0;

    for (int i =0; i<n; i++) {
        if (!(bitmask&(1<<i))) {
            memo[bitmask][last] = max(memo[bitmask][last], a[i]+c[last][i]+DP(i, bitmask | (1<<i), c));
        }
    }

    return memo[bitmask][last];
}


int32_t main() {
    fast_input;

    cin >> n >> m >> k;

    vector<vector<int>> c (n+1, vector<int>(n+1));
    memset(memo, -1, sizeof(memo));

    for (int i=0; i<n; i++) {
        int num;
        cin >> num;
        a.push_back(num);
    }

    for (int i =0; i<k; i++) {
        int ii, j, ci;
        cin >> ii >> j >> ci;

        c[ii-1][j-1] = ci;
    }

    // for (int i=0; i<100000; i++) {
    //     for (int j=0; j<10; j++) {
    //         cout << memo[i][j] << " ";
    //     }
    //     cout <<  endl;
    // }

    cout << DP(n,0, c) << endl;
    
    return 0;
}